/*
 * @lc app=leetcode.cn id=22 lang=cpp
 *
 * [22] 括号生成
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    vector<char> broad = {'(',')'};
    string tmp;
    vector<string> ret;
    void dfs(int n,int left,int right) {
        if(tmp.length() == n * 2) {
            ret.push_back(tmp);
            return ;
        }
        if(left < n) {
            tmp.push_back(broad[0]);
            dfs(n,left + 1,right);
            tmp.pop_back();
        }
        //如果右括号的使用小于左括号才能添加右括号
        if(right < left) {
            tmp.push_back(broad[1]);
            dfs(n,left,right+1);
            tmp.pop_back();
        }
        
    }
    vector<string> generateParenthesis(int n) {
        dfs(n,0,0);
        return ret;
    }
};
// @lc code=end

